package it.storm.solution;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 1725. 可以形成最大正方形的矩形数目
 * https://leetcode-cn.com/problems/number-of-rectangles-that-can-form-the-largest-square/
 */
public class Solutions_1725 {
    public static void main(String[] args) {
        int[][] rectangles1 = {{5, 8}, {3, 9}, {5, 12}, {16, 5}};  // output: 3
        int[][] rectangles2 = {{2, 3}, {3, 7}, {4, 3}, {3, 7}};  // output: 3

        List<int[][]> inputs = new ArrayList<>();
        inputs.add(rectangles1);
        inputs.add(rectangles2);

        for (int[][] input : inputs) {
            int result = countGoodRectangles(input);
            System.out.println(result);
        }
    }

    /**
     * 解法二：一次扫描（ms）
     */
    public static int countGoodRectangles(int[][] rectangles) {
        int max = 0, cnt = 0;
        for (int[] rect : rectangles) {
            int min = Math.min(rect[0], rect[1]);
            if (min > max) {
                max = min;
                cnt = 1;
            } else if (min == max) {
                cnt ++;
            }
        }
        return cnt;
    }

    /**
     * 解法一：哈希表（10ms）
     */
    public static int countGoodRectangles2(int[][] rectangles) {
        // {5, 3}：表示边长为 5 的正方形有 3 个
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] rect : rectangles) {
            int min = Math.min(rect[0], rect[1]);
            int cnt = map.getOrDefault(min, 0) + 1;
            map.put(min, cnt);
        }
        // 最大边长和最大边长的个数
        int max = 0, cnt = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getKey() > max) {
                max = entry.getKey();
                cnt = entry.getValue();
            }
        }
        // 返回最大边长的正方形个数
        return cnt;
    }
}
